package leetcode.cn;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/10/18 18:45
 * @注释:1089.复写零
 */
public class PrintTwoZero {
    /*
    给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：
输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]
*/


    //自己写的代码---no!
    public static void duplicateZeros1(int[] arr) {
        //首先找到最后一个需要复写的位置
        int cur = -1;//当前访问的位置
        int dest = -1;//复写后的长度
        int n = arr.length;
        while(dest!=n-1){
            cur++;
            if(arr[cur] == 0){
                dest+=2;
                if(dest >= n) break;
//                arr[dest] = 0;
            }else{
                dest++;
//                arr[dest] = arr[cur];
            }
        }
        //因为cur每次都是++到下一个，所以结束后要--
        //判断：如果dest=n，则【n-1】=0；cur--；dest-=2；再判断cur的值
        if(dest >= n && arr[cur] == 0){
            arr[n-1] = 0;
            cur--;
            dest-=2;
        }
        //从后向前复写
        while(dest>=0){
            if(arr[cur] == 0){
                arr[dest] = 0;
                arr[dest-1] = 0;
                dest-=2;
                cur--;
            }else{
                arr[dest] = arr[cur];
                cur--;
                dest--;
            }
        }
    }

    //最优解--Yes!!!
    public static void duplicateZeros(int[] arr) {
        //首先找到最后一个需要复写的位置
        int cur = 0;//当前访问的位置
        int dest = -1;//复写后的长度
        int n = arr.length;
        while (cur < n) {
            if (arr[cur] == 0) dest += 2;
            else dest++;
            //先别急着移动cur，判断一下dest的位置关系
            if (dest >= n - 1) break;
            cur++;
        }
        //处理一下边界i情况
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //从后往前复写
        while (cur >= 0) {
            if (arr[cur] == 0) {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            } else {
                arr[dest--] = arr[cur--];
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,0,2,3,0,4,5,0};
        duplicateZeros(arr);
        for (int i :
                arr) {
            System.out.print(i);
        }
    }
}
